package algorithm;

public class FloydWarshall implements Algorithm{
	
	private int[][] adjacencyMatrix;
	private int[][] predecessorMatrix;
	
	public  FloydWarshall(int[][] initial_matrix_){
		this.adjacencyMatrix = initial_matrix_;
		this.predecessorMatrix = null;
	}
	
	public FloydWarshall(){}
	
	@Override
	public int[][] run_all_pairs(){
		
		if(this.adjacencyMatrix == null)
			return null;
		
		int n = this.adjacencyMatrix.length;
		int[][] D0 = this.adjacencyMatrix;
		int[][] current_D = D0;
		int[][] prev_D;
				
		//the predecessor matrix, in order to construct the shortest path 
		int[][] predecessorMatrix0 = new int[n][n]; 
		int[][] current_predecessorMatrix = predecessorMatrix0;
		int[][] prev_predecessorMatrix;
		
		//initialize the predecessor matrix
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j || this.adjacencyMatrix[i][j] >= 101)
					predecessorMatrix0[i][j] = 101;
				else if(i != j && this.adjacencyMatrix[i][j] < 101)
					predecessorMatrix0[i][j] = i;
			}
		}
		
		/*
		 * Floyd Warshall All-Pairs Algorithm & 
		 *Construction of the shortest path
		 */ 
		for(int k = 0; k < n; k++){
			if( k == 0){
				current_D = D0;
				prev_D = D0;
				current_predecessorMatrix = predecessorMatrix0;
				prev_predecessorMatrix = predecessorMatrix0;
			}
			else{
				prev_D = current_D;
				prev_predecessorMatrix = current_predecessorMatrix;
			}
			 for(int i = 0; i < n; i++){
				 for(int j = 0; j < n; j++){
					 //updating the predecessor
					 if(prev_D[i][j] <= prev_D[i][k] + prev_D[k][j])
						 current_predecessorMatrix[i][j] = prev_predecessorMatrix[i][j];
					 else
						 current_predecessorMatrix[i][j] = prev_predecessorMatrix[k][j];
					 //update the cost of the shortest path
					 current_D[i][j] = Math.min(prev_D[i][j], prev_D[i][k] + prev_D[k][j]);
					
				 }
			 }
		}
		
		this.predecessorMatrix = current_predecessorMatrix;
		
		return current_D;
	}
	
	@Override
	public int[][] getPredecessorMatrix(){
		return this.predecessorMatrix;
	}
	
	

}
